package com.example.sort;

/**
 * Created by Quincy on 2018/9/11.
 * shell排序的时间复杂度：
 * shell排序的时间复杂度是根据选中的 增量d 有关的，所以分析shell排序的时间复杂度是个比较麻烦的事；这里只给出答案，不推算了；
 * 在最优的情况下，时间复杂度为：O（n ^ (1.3) ） （元素已经排序好顺序）
 * 在最差的情况下，时间复杂度为：O（n ^ 2）；
 */
public class ShellSort {

    private ShellSort(){}

    public static void sort1(Comparable[] arr){
        int n = arr.length;
        for (int h = n/2; h > 0; h = h/2){
            for (int i = 0; i < n; i++){
                int j;
                Comparable e = arr[i];
                for (j = i; j > 0 && arr[j-1].compareTo(e) > 0; j--)
                    swap(arr, j, j-1);
                arr[j] = e;
            }
        }
    }

    public static void sort2(Comparable[] arr){

        int n = arr.length;

        // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
        int h = 1;
        while (h < n/3) h = 3*h + 1;

        while (h >= 1) {

            // h-sort the array
            for (int i = h; i < n; i++) {

                // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
                Comparable e = arr[i];
                int j = i;
                for ( ; j >= h && e.compareTo(arr[j-h]) < 0 ; j -= h)
                    arr[j] = arr[j-h];
                arr[j] = e;
            }

            h /= 3;
        }
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}
